<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>快速排序之迭代实现</title>
</head>
<body>
  <script type="text/javascript">
    function quickSort(arr, startIndex, endIndex) {
      // 用一个栈来代替函数的递归栈
      const stack = [];
      // 整个数组的起止下标，以哈希的形式入栈
      const indexMap = new Map();
      indexMap.set('startIndex', startIndex);
      indexMap.set('endIndex', endIndex);
      stack.push(indexMap);

      // 循环结束条件：栈为空时
      while (stack.length) {
        // 栈顶元素出栈，得到起止下标
        const map = stack.pop();
        // 得到基准元素位置
        const pivotIndex = partition(arr, map.get('startIndex'), map.get('endIndex'));
        // 根据基准元素分成两部分, 把每一部分的起止下标入栈
        if (map.get('startIndex') < pivotIndex - 1) {
          const leftMap = new Map();
          leftMap.set('startIndex', map.get('startIndex'));
          leftMap.set('endIndex', pivotIndex - 1);
          stack.push(leftMap);
        }
        if (pivotIndex + 1 < map.get('endIndex')) {
          const rightMap = new Map();
          rightMap.set('startIndex', pivotIndex + 1);
          rightMap.set('endIndex', map.get('endIndex'));
          stack.push(rightMap);
        }
      }

      /*
       * 分治（单边循环法）
       * @param arr 待交换的数组
       * @param startIndex 起始下标
       * @param endIndex 结束下标
       */
      function partition(arr, startIndex, endIndex) {
        // 取第1个位置(也可以选择随机位置)的元素作为基准元素
        const pivot = arr[startIndex];
        let mark = startIndex;

        for (let i = startIndex + 1; i <= endIndex; i++) {
          if (arr[i] < pivot) {
            mark++;
            const temp = arr[mark];
            arr[mark] = arr[i];
            arr[i] = temp;
          }
        }

        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
      }
    }

    const arr = [10, 6, 3, 4, 8, 1, 2];
    quickSort(arr, 0, arr.length - 1);
    console.log(arr);
  </script>
</body>
</html>